package hot100.接雨水;

/**
 * @author llt
 * @date 2025/5/13
 */
public class Test {
    public int trap(int[] height) {
        // 将蓝色和黑色看做一个整体(maxArr) 必然有一个最高值 根据最高位置 求每个位置的高度 数组相减求和
        // 左边方程 maxArr[i] = Math.max(maxArr[i - 1], height[i]);
        // 右边方程 maxArr[i] = Math.max(maxArr[i + 1], height[i]);
        int len = height.length;
        if(len <= 2) {
            return 0;
        }

        // 记录最大值的下标
        int max = height[0];
        int maxIndex = 0;
        for(int i = 1; i < len; i++) {
            if(max < height[i]) {
                max = height[i];
                maxIndex = i;
            }
        }

        int[] maxArr = new int[len];
        // 求最大值左边数组
        maxArr[0] = height[0];
        for(int i = 1; i <= maxIndex; i++) {
            maxArr[i] = Math.max(maxArr[i - 1], height[i]);
        }
        // 求最大值右边数组
        maxArr[len - 1] = height[len - 1];
        for(int i = len - 2; i > maxIndex; i--) {
            maxArr[i] = Math.max(maxArr[i + 1], height[i]);
        }

        int result = 0;
        for(int i = 0; i < len; i++) {
            result += maxArr[i] - height[i];
        }

        return result;
    }
}
